package com.kl.trie;

import org.apache.commons.lang3.CharUtils;

import java.util.HashMap;

/**
 * 缺点：空间消耗大
 *
 * @param <V>
 */
public class TrieImpl<V> implements Trie<V> {

    // 树中的结点数量
    private int size;
    // 根节点：不存储数据
    private final Node<V> root = new Node<>(null);


    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        size = 0;
    }

    @Override
    public V get(String str) {
        Node<V> node = getNode(str);
        if (node != null && node.word) {
            return node.value;
        }
        return null;
    }

    @Override
    public boolean contains(String str) {
        Node<V> node = getNode(str);
        return node != null && node.word;
    }

    @Override
    public V add(String str, V value) {
        checkKey(str);

        Node<V> node = root;
        int len = str.length();
        for (int i = 0; i < len; i++) {
            char c = str.charAt(i);
            Node<V> child = node.getChildren().get(c);
            if (child == null) {
                // 新增结点
                child = new Node<>(node);
                child.character = c;
                node.getChildren().put(c, child);
            }
            // 不论新增与否都要向下一层结点查找
            node = child;
        }

        // 该结点之前已经添加过的情况
        if (node.word) {
            V oldValue = node.value;
            node.value = value;
            return oldValue;
        }

        // 该结点是第一次添加，那么在最后一个结点位置存放value
        node.value = value;
        node.word = true;
        size++;
        return null;
    }

    /**
     * 注意：
     * 1、必须是一个单词才能删除，通过word是否为true来判断
     * 2、在删除一个单词时由于这个单词的一部分跟其他单词有交集，那么就不能把有交集的那部分单词删除
     * 可以先判断这个要删除的单词是否存在，如果存在的话就从下往上进行删除，对于当前要删除的字符有子结点的情况就说明与其他
     * 单词有交集，那么就退出删除逻辑，否则继续往父结点删除
     * 3、还有一种情况是，准备删除的结点没有其他子结点了，但以这个结点结尾的可能也是一个单词，也就是当前要删除的单词包含了其他单词
     */
    @Override
    public V remove(String str) {
        checkKey(str);
        Node<V> node = getNode(str);
        // 单词都不存在或者都不是一个单词
        if (node == null || !node.word) return null;
        // 单词存在，但是这个单词后还有子结点关联
        V oldValue = node.value;
        if (node.children != null && !node.children.isEmpty()) {
            node.word = false;
            node.value = null;
            return oldValue;
        }

        // 从下往上删除结点
        Node<V> parent;
        while ((parent = node.parent) != null) {
            node.parent.children.remove(node.character);
            // 删除当前结点后，如果父结点是一个单词或者父结点还有其他关联的单词就可以停止删除
            if (parent.word || !parent.children.isEmpty()) break;
            node = parent;
        }
        return oldValue;
    }

    @Override
    public boolean startWith(String prefix) {
        checkKey(prefix);
        return getNode(prefix) != null;
    }

    private Node<V> getNode(String str) {
        checkKey(str);

        int len = str.length();
        Node<V> node = root;
        for (int i = 0; i < len; i++) {
            // 循环取出每一个字符
            char c = str.charAt(i);
            // 判断该字符是否存在当前结点的子结点中
            node = node.getChildren().get(c);
            if (node == null) return null;
        }
        return node;
    }

    private void checkKey(String key) {
        if (key == null || key.length() == 0) {
            throw new IllegalArgumentException("参数不能为空");
        }
    }

    /**
     * 敏感词过滤
     * 根据已经创建的前缀树来过滤树中存在的单词
     */
    public String filter(String str) {
        checkKey(str);
        StringBuilder builder = new StringBuilder();
        Node<V> node = root;
        int left = 0;
        int right = 0;
        int len = str.length();
        while (left < len) {
            char c = str.charAt(right);
            if (isSymbol(c)) {
                if (node == root) {
                    builder.append(c);
                    left++;
                }
                right++;
                continue;
            }
            Node<V> child = node.getChildren().get(c);
            // 发现了有敏感词起始结点，说明之后可能会出现敏感词
            if (child != null) {
                // 顺着结点往下找，并扩大搜索的范围
                node = child;
                right++;
                if (node.word) {
                    while (left < right) {
                        builder.append("*");
                        left++;
                    }
                    node = root;
                }
            } else {
                // 没有找到敏感词起始结点，说明当前单词一定不是敏感词
                builder.append(str.charAt(left++));
                node = root;
                right = left;
            }
        }
        return builder.toString();
    }

    // 判断是否为符号
    private boolean isSymbol(Character c) {
        // 0x2E80~0x9FFF 是东亚文字范围
        return !CharUtils.isAsciiAlphanumeric(c) && (c < 0x2E80 || c > 0x9FFF);
    }

    private static class Node<V> {
        V value;      // 结点存储的数据
        boolean word; // 是否为单词的结尾
        Node<V> parent;
        Character character;
        HashMap<Character, Node<V>> children;

        public Node(Node<V> parent) {
            this.parent = parent;
        }

        // 保证存储子结点的哈希表不为空，可以减少很多判断
        public HashMap<Character, Node<V>> getChildren() {
            return children != null ? children : (children = new HashMap<>());
        }
    }


}
